In the area of general digital signatures, the most common signature schemes are RSA and the U.S. Digital Signature Algorithm over elliptic curves (ECDSA). The RSA algorithm, with appropriate parameters, can be quite fast at verification, but generating signatures is slow. Further, signatures in RSA are at least one kilobyte in size, making them unsuited for SIM cards or for product registration.
A scheme for “online/offline” digital signatures was proposed by Shamir and Tauman. See A. Shamir & Y. Tauman, “Improved Online-Offine Signature Schemes,” CRYPTO 2001. Their scheme made use of chameleon hash functions and introduced the “Hash-Sign-Switch” paradigm that may be used for efficient generation of provisional signatures. They did not, however, consider the application of their scheme to the case of having a server assist in the process.
In server assisted digital signatures, it is desirable to reduce the computational and communication overhead required for a signature by employing a separate server. This is known as Server Assisted Signatures (SAS). Naturally, one can imagine a number of alternate scenarios wherein efficient digital signatures are desired and some third party is available. The issue of reducing signer communication and computation is of immediate practical interest because it allows for more efficient energy usage and, therefore, longer lifetime for mobile devices. Many previously proposed SAS schemes have been found insecure, while others require the signer to communicate a large amount of data per signature or require the server to store a large amount of state per client.
An example application for SAS is product registration. A signer may wish to dispense an authorization key for a piece of software or for a newly purchased phone. The verifier comprises the software itself, which is assumed to have connectivity to the server. The authorization key consists of a signature on the software itself plus a serial number. The digital signature is further typed on a piece of paper or a label shipped with the software.
Another example application for SAS is UIM cards. A UIM card is a smart card containing a processor and a small amount of storage. UIM cards allow the user to maintain a single identity when moving from device to device, such as from one phone to another or from a phone to a PC. In addition, UIM cards are used in FirstPass SSL client authentication, which uses RSA to authenticate a user to a web site. Current UIM cards require special purpose processors to perform RSA digital signatures and may take up to half a second for each signature. Furthermore, an RSA secret key takes one kilobyte of space on the UIM card, and so the number of keys on the card is limited to five.
Previous solutions to the server-assisted signature problem have several drawbacks. A scheme by Beguin and Quisquater was shown to be insecure by Nguyen and Stem. Therefore, it cannot be considered for practical use. For more information, see P. Nguyen and J. Stem, “The Beguin-Quisquater Server-Aided RSA Protocol from Crypto'95 is not Secure,” Asiacrypt 1998 and P. Beguin and J. J. Quisquater, “Fast server-aided RSA signatures secure against active attacks,” CRYPTO 1995. A method by Jakobsson and Wetzel appears secure, but is limited to use for only DSA and ECDSA, because signatures are at least 320 bits in size. See M. Jakobsson and S. Wetzel, “Secure Server-Aided Signature Generation,” International Workshop on Practice and Theory in Public Key Cryptography, 2001.
A scheme by Bicacki and Bayal requires the server to store five kilobytes per signer per signature. See Bicacki & Bayal, “Server Assisted Signatures Revisited,” RSA Cryptographers' Track 2003. If there were, for example, 80 million signers, each of whom produce 10 signatures per day, this requires storing roughly 3.7 terabytes per day. The scheme of Goyal addresses this problem and requires 480 bits of server storage per signature. See, V. Goyal, “More Efficient Server Assisted Signatures,” Cryptography Eprint Archive, 2004. With 80 million signers, 10 signatures per day, this scheme requires roughly 357 gigabytes per day.
Worse, in both schemes, the amount of data the server must store increases without bound. This is because the data is kept in case the server is accused of cheating by some signer. Therefore, the data must be kept until the server is sure it cannot be accused of cheating, which in practice may be months or years. Assuming a “statute of limitations” period of one year, Goyal's scheme requires more than 127 terabytes of server storage. If any data is missing and a signature is challenged, the server will be unable to prove it acted correctly.
Another drawback of both the Goyal and the Bicacki-Bayal schemes is that the signer must send a public key for a one-time signature to the server for each message. With the suggested embodiment of Goyal's paper, this requires 26 kilobytes of communication per signature. This large communication makes the product registration application infeasible.
Another type of signature is a designated confirmer signature. In designated confirmer digital signatures, a signature on a message cannot be verified without the assistance of a special “designated confirmer.” The signer selects the designated confirmer when the signature is generated. The designated confirmer can then take a signature and either confirm that the signature is genuine, or disavow a signature that was not actually created by the signer, but the confirmer cannot generate any new signatures. Further, the confirmer can convert a signature into a regular signature that can be verified by anyone.
An example application of using a designated confirmer is the signing of electronic contracts. A job candidate and a potential employer may negotiate an employment contract without being physically present in the same room. The employer would prefer that the employee not use the contract as a bargaining tool with other prospective employers. Therefore, the employer can sign using a designated confirmer signature and designate a court of law as the confirmer. That way, if a dispute arises, the signature can be verified, but the signature cannot be verified in the meantime by other employers. After both parties have finalized the contract, the signature can be converted to a regular signature.
Another example application for use of a designated confirmer is the verification of software patches. A software vendor may wish to restrict software patches only to users who have properly paid for software. One method of accomplishing this restriction is to sign patches with a designated confirmer signature scheme and provide confirmation only to registered users. Unregistered users cannot verify the signature and run the risk of installing compromised software patches.
Most previous implementations of designated confirmer digital signatures use special-purpose properties of algorithms such as RSA. If these specific algorithms are found insecure, then these schemes are also insecure. Goldwasser and Waisbard showed how to convert several existing signature schemes into designated confirmer signature schemes. See, S. Golwasser and E. Waisbard, “Transformation of Digital Signature Schemes into Designated Confirmer Signature Schemes,” Theory of Cryptography Conference, 2004.
Another type of signature is a blind signature. In blind digital signatures, the signer signs a “blinded” version X of the message M. The blinded version X is generated with the aid of a blinding factor r. A blinder wishes to obtain a signature on a message M without revealing M to the signer. This is achieved by the blinded asking the signer to sign a message X, which is the “blinded version” of M. After signing, the signature can be “unblinded” using the blinding factor to obtain a signature on M. Without the blinding factor, it is infeasible to link a signature on the blinded message X with a signature on the un-blinded message M. From the signature on X, the blinder can then recover a signature on M. The signature on X as the “provisional signature,” and the signature on M as the “final signature.”
An example application of blind signatures is unlinkable electronic cash tokens. Our goal is to enhance user privacy by ensuring not even the bank can track different transactions. The user creates a token for a certain denomination and then blinds the token. The bank signs the blinded token and returns it to the user, who unblinds to obtain the bank's signature on a token. With the token and bank's signature on the token, the user can partake in a financial transaction since a third party can verify the bank's signature. On the other hand, because the bank signed the blinded token, it cannot trace the token back to the user, hence providing anonymity for the user. To avoid cheating users, a cut and choose protocol may be used in which the user generates 100 or more tokens of the same denomination and the bank asks to see 99 of them, chosen randomly, before signing the last token.